/*-------------------------------------------------------------------------
 *
 * hashsort.c
 *		对要插入新哈希索引的元组进行排序。
 *
 * 在构建非常大的哈希索引时，我们按桶编号对元组进行预排序，以提高对索引的访问局部性，从而避免抖动。
 * 我们使用tuplesort.c将给定的索引元组排序。
 *
 * 注意：如果表中的行数被低估，则在索引构建期间可能会发生桶拆分。在这种情况下，我们将为每个可能的掩码哈希码值插入到两个或多个桶中。
 * 这并不是大问题，因为我们仍然会有足够的访问局部性。
 *
 *
 * Portions Copyright (c) 1996-2022, PostgreSQL Global Development Group
 * Portions Copyright (c) 1994, Regents of the University of California
 *
 * IDENTIFICATION
 *	  src/backend/access/hash/hashsort.c
 *
 *-------------------------------------------------------------------------
 */

#include "postgres.h"

#include "access/hash.h"
#include "commands/progress.h"
#include "miscadmin.h"
#include "pgstat.h"
#include "port/pg_bitutils.h"
#include "utils/tuplesort.h"


/*
 * 排队/排序阶段的状态记录。
 */
struct HSpool
{
	Tuplesortstate *sortstate;	/* tuplesort.c的状态数据 */
	Relation	index;

	/*
	 * 我们根据键所属的桶来对哈希键进行排序。下面的掩码
	 * 用于 _hash_hashkey2bucket 来确定给定哈希键的桶。
	 */
	uint32		high_mask;
	uint32		low_mask;
	uint32		max_buckets;
};


/*
 * 创建并初始化一个排队结构
 */
HSpool *
_h_spoolinit(Relation fc_heap, Relation fc_index, uint32 fc_num_buckets)
{
	HSpool	   *fc_hspool = (HSpool *) palloc0(sizeof(HSpool));

	fc_hspool->index = fc_index;

	/*
	 * 确定哈希码值的位掩码。由于当前在索引中有
	 * num_buckets 个桶，因此可以按如下方式计算合适的掩码。
	 *
	 * 注意：此哈希掩码计算应与 _hash_init_metabuffer 中的
	 * 类似计算保持同步。
	 */
	fc_hspool->high_mask = pg_nextpower2_32(fc_num_buckets + 1) - 1;
	fc_hspool->low_mask = (fc_hspool->high_mask >> 1);
	fc_hspool->max_buckets = fc_num_buckets - 1;

	/*
	 * 我们将排序区域的大小设置为 maintenance_work_mem 而
	 * 不是 work_mem，以加快索引创建。这应该是可以的，
	 * 因为单个后端不能并行运行多个索引创建。
	 */
	fc_hspool->sortstate = tuplesort_begin_index_hash(fc_heap,
												   fc_index,
												   fc_hspool->high_mask,
												   fc_hspool->low_mask,
												   fc_hspool->max_buckets,
												   maintenance_work_mem,
												   NULL,
												   TUPLESORT_NONE);

	return fc_hspool;
}

/*
 * 清理排队结构及其子结构。
 */
void _h_spooldestroy(HSpool *fc_hspool)
{
	tuplesort_end(fc_hspool->sortstate);
	pfree(fc_hspool);
}

/*
 * 将索引条目放入排序文件中。
 */
void _h_spool(HSpool *fc_hspool, ItemPointer fc_self, Datum *fc_values, bool *fc_isnull)
{
	tuplesort_putindextuplevalues(fc_hspool->sortstate, fc_hspool->index,
								  fc_self, fc_values, fc_isnull);
}

/*
 * 给定通过连续调用 _h_spool 加载的排队，
 * 创建整个索引。
 */
void _h_indexbuild(HSpool *fc_hspool, Relation fc_heapRel)
{
	IndexTuple	fc_itup;
	int64		fc_tups_done = 0;
#ifdef USE_ASSERT_CHECKING
	uint32		fc_hashkey = 0;
#endif

	tuplesort_performsort(fc_hspool->sortstate);

	while ((fc_itup = tuplesort_getindextuple(fc_hspool->sortstate, true)) != NULL)
	{
		/*
		 * 从技术上讲，哈希键的排序顺序并不是关键，
		 * 因为此排序仅用于提高访问的局部性作为性能优化。
		 * 不过，似乎通过断言测试 tuplesort.c 对哈希索引
		 * 元组排序的处理是个好主意。
		 */
#ifdef USE_ASSERT_CHECKING
		uint32		fc_lasthashkey = fc_hashkey;

		fc_hashkey = _hash_hashkey2bucket(_hash_get_indextuple_hashkey(fc_itup),
									   fc_hspool->max_buckets, fc_hspool->high_mask,
									   fc_hspool->low_mask);
		Assert(fc_hashkey >= fc_lasthashkey);
#endif

		_hash_doinsert(fc_hspool->index, fc_itup, fc_heapRel);

		/* 允许插入阶段被中断，并跟踪进度 */
		CHECK_FOR_INTERRUPTS();

		pgstat_progress_update_param(PROGRESS_CREATEIDX_TUPLES_DONE,
									 ++fc_tups_done);
	}
}
